package pers.qianyu.month_202012.date_20201224;

import org.junit.*;

import java.util.*;

/**
 * 452. 用最少数量的箭引爆气球
 * https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/submissions/
 *
 * @author mizzle rain
 * @date 2020年12月24日21:19:13
 */
public class FindMinArrowShots {
    public int findMinArrowShots(int[][] points) {
        int len = points.length;
        if (len == 0) {
            return 0;
        }
        Arrays.sort(points, (arr1, arr2) -> {
            return arr1[0] - arr2[0];
        });
        int[] interval = new int[]{points[0][0], points[0][1]};
        int count = 1;
        for (int i = 1; i < len; i++) {
            int[] point = points[i];
            if (interval[0] <= point[1] && interval[1] >= point[0]) {
                interval[0] = point[0];
                if (point[1] < interval[1]) {
                    interval[1] = point[1];
                }
            } else {
                interval = new int[]{point[0], point[1]};
                count++;
            }
        }
        return count;
    }

    @Test
    public void test1() {
        int[][] arr = {
                {10, 16}, {2, 8}, {1, 6}, {7, 12}
        };
        int result = new FindMinArrowShots().findMinArrowShots(arr);
        System.out.println("result = " + result);
    }
}